#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> prefixLenMap;
        int numsSize = nums.size();
        int prefixLen = 0;
        int ret = 0;
        prefixLenMap[0] = 1;
        
        for (int i = 0; i < numsSize; i++) {
            prefixLen += nums[i];
            
            if (prefixLenMap.count(prefixLen - k)) {
                ret += prefixLenMap[prefixLen - k];
            }
            
            prefixLenMap[prefixLen]++;
        }
        
        return ret;
    }
};

int main()
{
    vector<int> nums = {-1, -1, 1};
    Solution solution;
    std::cout << solution.subarraySum(nums, 0) << std::endl;
}